package com.sheng.leetcode.year2023.month02.day15;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/02/15
 * <p>
 * 1250. 检查「好数组」<p>
 * <p>
 * 给你一个正整数数组 nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个 任意整数，并求出他们的和。<p>
 * 假如该和结果为 1，那么原数组就是一个「好数组」，则返回 True；否则请返回 False。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [12,5,7,23]<p>
 * 输出：true<p>
 * 解释：挑选数字 5 和 7。<p>
 * 5*3 + 7*(-2) = 1<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [29,6,10]<p>
 * 输出：true<p>
 * 解释：挑选数字 29, 6 和 10。<p>
 * 29*1 + 6*(-3) + 10*(-1) = 1<p>
 * <p>
 * 示例 3：<p>
 * 输入：nums = [3,6]<p>
 * 输出：false<p>
 * <p>
 * 提示：<p>
 * 1 <= nums.length <= 10^5<p>
 * 1 <= nums[i] <= 10^9<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/check-if-it-is-a-good-array">1250. 检查「好数组」</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1250 {

    @Test
    public void test01() {
//        int[] nums = {12, 5, 7, 23};
//        int[] nums = {29, 6, 10};
        int[] nums = {3, 6};
        System.out.println(new Solution().isGoodArray(nums));
    }
}

class Solution {
    public boolean isGoodArray(int[] nums) {
        /**
         * 我们先可以考虑选取两个数的情况，若选取的数是 a 和 b，那么根据题目的要求，我们需要满足
         * a×x+b×y=1，其中 x 和 y 是任意整数。根据裴蜀定理，可以得知，如果 a 和 b 互质，那么上述等式一定有解。实际上，裴蜀定理也可以推广到多个数的情况，即如果
         * a1,a2,...,ai 互质，那么 a1 * x1 + a2 * x2 + ... + ai * xi = 1 一定有解，其中 x1, x2,..., xi是任意整数。
         * 因此，我们只需要判断在数组 nums 中是否存在 i 个互质的数即可。两个数互质的充要条件是它们的最大公约数为 1。如果数组 nums 存在 i 个互质的数，
         * 那么数组 nums 中的所有数的最大公约数也为 1。
         * 所以我们将题目转化为：判断数组 nums 中的所有数的最大公约数是否为 1 即可。遍历数组 nums，求出数组 nums 中的所有数的最大公约数即可。
         *
         * 作者：lcbin
         * 链接：https://leetcode.cn/problems/check-if-it-is-a-good-array/solution/python3javacgo-yi-ti-yi-jie-shu-xue-pei-3f4da/
         * 来源：力扣（LeetCode）
         * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
         */
        int g = 0;
        for (int x : nums) {
            g = gcd(x, g);
        }
        return g == 1;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

